SPOJ/MDIGITS - 3928. Counting Digits/4808.cpp

   1 // 4808 from Live Archive
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 vector<int> num;
  29
  30
  31 void print(const vector<int> &v) {
  32     for (int i = 0; i < v.size(); ++i) {
  33         if (i > 0) printf(" ");
  34         printf("%d", v[i]);
  35     }
  36     printf("\n");
  37 }
  38
  39 int ten(int e) {
  40     assert(e >= 0);
  41     int ans = 1;
  42     while (e--) ans *= 10;
  43     return ans;
  44 }
  45
  46 int assemble(int i) {
  47     assert(i >= -1);
  48     int ans = 0;
  49     for (int k = i; k >= 0; --k) {
  50         ans = 10 * ans + num[k];
  51     }
  52     return ans;
  53 }
  54
  55 vector<int> memo[10][2];
  56
  57 vector<int> f(int i, bool m) {
  58     if (i < 0) {
  59         return vector<int>(10, 0);
  60     }
  61
  62     if (memo[i][m].size() > 0) return memo[i][m];
  63
  64     vector<int> ans(10, 0);
  65
  66     int limit = (m ? 9 : num[i] - 1);
  67     for (int k = 0; k <= limit; ++k) {
  68         vector<int> s = f(i - 1, true);
  69         s[k] += ten(i);
  70         for (int j = 0; j < 10; ++j) ans[j] += s[j];
  71     }
  72
  73     if (!m) {
  74         vector<int> s = f(i - 1, false);
  75         s[num[i]] += assemble(i - 1) + 1;
  76         for (int j = 0; j < 10; ++j) ans[j] += s[j];
  77     }
  78     memo[i][m] = ans;
  79     return ans;
  80 }
  81
  82 vector<int> f(int x) {
  83     num.clear();
  84     while (x > 0) num.push_back(x % 10), x /= 10;
  85     for (int i = 0; i <= 10; ++i) {
  86         memo[i][0].clear(), memo[i][1].clear();
  87     }
  88     vector<int> ans = f(num.size() - 1, false);
  89     ans[0] -= (ten(num.size()) - 1) / 9;
  90     // for (int i = num.size() - 1; i >= 0; --i) {
  91     //     assert(ans[0] >= ten(i));
  92     //     ans[0] -= ten(i);
  93     // }
  94     return ans;
  95 }
  96
  97 void bruteforce(int a) {
  98     vector<int> ans(10, 0);
  99     for (int i = 1; i <= a; ++i){
 100         int x = i;
 101         while (x > 0) ans[x % 10]++, x /= 10;
 102     }
 103     printf("Bruteforced answer for i=%d: ", a);
 104     print(ans);
 105 }
 106
 107 int main(){
 108     // vector<int> a = f(1);
 109     // print(a);
 110     // for (int i = 1; i <= 100; ++i) {
 111     //     printf("i = %d: ", i);
 112     //     print(f(i));
 113     // }
 114     int a, b;
 115     while (cin >> a >> b) {
 116         if (a == 0 and b == 0) break;
 117         if (a > b) swap(a, b);
 118         vector<int> ans = f(b);
 119         if (a - 1 > 0) {
 120             vector<int> remove = f(a - 1);
 121             for (int i = 0; i < 10; ++i) ans[i] -= remove[i];
 122         }
 123         //if (a - 1 > 0) { printf("f(%d) = ", a - 1); print(f(a - 1)); }
 124         //printf("f(%d) = ", b); print(f(b));
 125         //bruteforce(b);
 126         print(ans);
 127     }
 128     return 0;
 129 }